#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int QueueDataType;

typedef struct QueueNode
{
	struct Queue* next;
	QueueDataType data;
}QueueNode;

typedef struct Quene
{
	QueueNode* head;
	QueueNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == NULL;
}

void QueuePush(Queue* pq,QueueDataType x)
{
	assert(pq);
	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
	node->data = x;
	node->next = NULL;

	if (QueueEmpty(pq))
	{
		pq->head = pq->tail = node;
	}
	else
	{
		pq->tail->next = node;
		pq->tail = node;
	}
	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->size > 1)
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	else
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	pq->size--;
}

QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int PartSort(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev < cur)
			Swap(&a[prev], &a[cur]);
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSort(int* a, int left, int right)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, left);
	QueuePush(&q, right);
	while (!QueueEmpty(&q))
	{
		int begin = QueueFront(&q);
		QueuePop(&q);
		int end = QueueFront(&q);
		QueuePop(&q);
		int keyi = PartSort(a, begin, end);
		if (begin < keyi - 1)
		{
			QueuePush(&q, begin);
			QueuePush(&q, keyi - 1);
		}
		if (keyi + 1 < end)
		{
			QueuePush(&q, keyi + 1);
			QueuePush(&q, end);
		}
	}
}

int main()
{
	int a[] = { 6,9,8,61,82,38,2,1,6,3,4,-6,-8,-1,-5,-4 };
	int len = sizeof(a) / sizeof(int);
	QuickSort(a, 0, len - 1);
	int i = 0;
	for (i = 0; i < len; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}